// Tags:
#include <cctype>
#include <cstdio>
#include <set>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 40;
int n, m, s[N], ans, lim;
std::set<int> set;

void dfs(int x, int sum, bool typ) {
  if (typ) {
    if (x > n) {
      auto it = --set.upper_bound(m - 1 - sum);
      ans = std::max(ans, *it + sum);
      return;
    }
  } else {
    if (x > lim) { return set.insert(sum), void(); }
  }
  dfs(x + 1, sum, typ);
  dfs(x + 1, (sum + s[x] >= m) ? sum - m + s[x] : sum + s[x], typ);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("stone.in", "r", stdin);
  freopen("stone.out", "w", stdout);
#endif
#endif

  lim = read(n) >> 1, read(m);
  for (int i = 1; i <= n; ++i) read(s[i]) %= m;
  dfs(1, 0, false);
  dfs(lim + 1, 0, true);
  printf("%d", ans);
  return 0;
}